package offer

import (
	. "GoLeetcode/common"
)

/*
时间复杂度:O(MN)
空间复杂度:O(MN)

首先遍历整个矩阵,如果遇到为1的元素,进行dfs,dfs过程中将于该1连通的区域都设置为2,表示已访问,同时统计连通区域的大小ans
每次遇到一块新的1区域,则统计面积,然后与ans进行比较取最大值

q:如何统计一块1的面积???
	设置成dfs的返回值, 一带一内部递归,带返回值

dfs使用先判后四方法
*/

type Pair struct {
	X int
	Y int
}

var dirs = [4]Pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func maxAreaOfIsland(grid [][]int) int {
	m, n := len(grid), len(grid[0])

	// 返回'1'的连通区域的面积大小
	var dfs func(x, y int) int
	dfs = func(x, y int) int {
		// grid[x][y] == 0表示非1的区域, grid[x][y] == 2表示已访问的1区域
		if x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0 || grid[x][y] == 2 {
			return 0
		}
		grid[x][y] = 2
		count := 0
		// 上下左右四个方向递归
		for _, d := range dirs {
			count += dfs(x+d.X, y+d.Y)
		}
		// +1加的是(x, y)这个点的面积
		return count + 1
	}

	ans := 0
	for i := range grid {
		for j := range grid[i] {
			if grid[i][j] == 1 {
				ans = Max(ans, dfs(i, j))
			}
		}
	}
	return ans
}
